5905. Корни из единицы

Как известно, существует ровно n комплексных корней n-ой степени из единицы. Обозначим эти корни через ω₀, ω₁, ..., ω_n-1. Напомним, что ω_k = .

Вам требуется определить по заданному комплексному числу z такой номер k, что ω_k = z.

Вход. В первой строке записано целое число n (1 ≤ n ≤ 100). Во второй строке записано два действительных числа a и b с девятью знаками после запятой. Гарантируется, что a + bi является корнем n-ой степени из единицы.

Выход. Выведите такое k, что ω_k = a + bi.

Пример входа

100

-0.125333234 -0.992114701

Пример выхода

73

РЕШЕНИЕ

комплексные числа

Анализ алгоритма

Поскольку значение n не велико, поиск искомого k можно совершить простым перебором. Примитивный корень n-ой степени из единицы равен ω₁ = = . Пусть z = a + bi – входное число. Будем последовательно перебирать корни из единицы ω₀, ω₁, ..., ω_n-1 до тех пор, пока одно из них не станет равным z.

Реализация алгоритма

Определим константы:

#define EPS 1e-7

#define PI acos(-1.0)

Функция сравнения двух комплексных чисел. Возвращает 1, если a = b. Два комплексных числа считаются равными, если их действительные и мнимые части отличаются друг от друга не больше чем на EPS.

int Equal(complex<double> a, complex<double> b)

{

double ReA = a.real(), ImA = a.imag();

double ReB = b.real(), ImB = b.imag();

return (fabs(ReA - ReB) < EPS) && (fabs(ImA - ImB) < EPS);

}

Основная часть программы. Читаем входные данные. Пусть z = a + bi, w = ω₀ = 1, e = ω₁.

scanf("%d",&n);

scanf("%lf %lf",&a,&b);

complex<double> z = complex<double>(a,b);

complex<double> w = complex<double>(1,0),

e = complex<double>(cos(2*PI/n),sin(2*PI/n));

Перебираем корни из единицы ω₀, ω₁, ω₂, ..., пока не найдется такое k, что ω_k = z.

while(!Equal(w,z))

{

w = w * e;

c++;

}

Выводим ответ.

printf("%d\n",c);